#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
int x[26], X[26];

void solve() {
	int n, k; cin >> n >> k;
	string s; cin >> s;
	memset(x, 0, sizeof x);
	memset(X, 0, sizeof X);
	for (int i = 0; i < n; i++) {
		if (s[i] >= 'a' && s[i] <= 'z') x[s[i] - 'a']++;
		else X[s[i] - 'A']++;
	}
	int ans = 0, sum = 0;
	for (int i = 0; i < 26; i++) {
		ans += min(x[i], X[i]);
		sum += abs(x[i] - X[i]) / 2;
	}
	ans += min(sum, k);
	cout << ans << endl;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int t; cin >> t;
	while (t--) {
		solve();
	}
	return 0;
}